#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    vector<int> sortArrayByParity(vector<int> &nums)
    {
        int i = 0;
        while (i < nums.size())
        {
            if (nums[i] % 2)
            {
                nums.emplace_back(nums[i]);
                // nums[i]=-1;
                nums.erase(nums.begin() + i);
            }
            i++;
        }
        return nums;
    }

    vector<int> sortArrayByParity_2(vector<int> &nums)
    {
        vector<int> res;
        for (auto &num : nums)
        {
            if (num % 2 == 0)
            {
                res.push_back(num);
            }
        }
        for (auto &num : nums)
        {
            if (num % 2 == 1)
            {
                res.push_back(num);
            }
        }
        return res;
    }

    vector<int> sortArrayByParity_3(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> res(n);
        int left = 0, right = n - 1;
        for (auto &num : nums)
        {
            if (num % 2 == 0)
            {
                res[left++] = num;
            }
            else
            {
                res[right--] = num;
            }
        }
        return res;
    }
    vector<int> sortArrayByParity_4(vector<int> &nums)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            while (left < right and nums[left] % 2 == 0)
            {
                left++;
            }
            while (left < right and nums[right] % 2 == 1)
            {
                right--;
            }
            if (left < right)
            {
                swap(nums[left++], nums[right--]);
            }
        }
        return nums;
    }

    /**
     * @brief 双指针
     *
     * @param nums
     * @return vector<int>
     */
    vector<int> sortArrayByParity_5(vector<int> &nums)
    {
        for (int l = 0, r = nums.size() - 1; l < r; l++)
            if (nums[l] & 1)
                swap(nums[l--], nums[r--]);
        return nums;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {3, 1, 2, 4};
    vector<int> ans = s.sortArrayByParity_5(nums);
    for (auto &v : ans)
    {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}